package cn.chen.sort;

import java.util.*;

public class Example {

    public static void bubbleSort(Comparable[] a){
        int N = a.length;
        for(int i = 0; i < N - 1;i ++){
            for(int j = i + 1;j < N;j ++){
                if(less(a[j],a[i])) exch(a,i,j);
            }
        }
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi){
        int i = lo, j = mid + 1;

        Comparable[] aux = Arrays.copyOf(a, a.length);

        for(int k = lo; k <= hi; k++){
            if(i > mid) a[k] = aux[j++];
            else if(j > hi) a[k] = aux[i++];
            else if(less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    public static void selectionSort(Comparable[] a){
        int N = a.length;
        for(int i = 0;i < N;i ++){
            int min = i;
            for(int j = i + 1;j < N;j ++)
                if(less(a[j],a[min])) min = j;
            exch(a,i,min);
        }
    }

    public static void insertSort(Comparable[] a){
        int N = a.length;
        for(int i = 1;i < N;i ++){
            for(int j = i;j > 0 && less(a[j],a[j - 1]);j --) exch(a, j, j-1);
        }
    }

    public static void insertSort2(Comparable[] a){
        int N = a.length;
        for(int i = 1;i < N;i ++){
            int j = i;
            Comparable temp = a[i];
            for(;j > 0 && less(temp, a[j - 1]);j --) {
                shiftRight(a, j - 1);
            }
            a[j] = temp;
        }
    }

    public static void shellSort(Comparable[] a){
        int N = a.length;
        int h = 1;
        while(h < N / 3) h = 3 * h + 1;
        while(h >= 1){
            for(int i = h;i < N; i++){
                for(int j = i; j >= h && less(a[j],a[j-h]);j -= h){
                    exch(a, j, j-h);
                }
            }
            h = h / 3;
        }
    }

    public static long time(String alg,Comparable[] a){
        long start = System.currentTimeMillis();
        if(alg.equals("insert1"))insertSort(a);
        if(alg.equals("insert2"))insertSort2(a);
        if(alg.equals("bubble"))bubbleSort(a);
        if(alg.equals("select"))selectionSort(a);
        if(alg.equals("shell"))shellSort(a);
        if(alg.equals("merge"))merge(a, 0,a.length / 2,a.length - 1);
//        if(alg.equals("quick"))insertSort2(a);
//        if(alg.equals("heap"))insertSort2(a);
        long end = System.currentTimeMillis();
        return end - start;
    }

    private static void shiftRight(Comparable[] a,int i){
        a[i + 1] = a[i];
    }

    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void show(Comparable[] a){
        for(int i = 0;i < a.length;i ++) System.out.print(a[i] + " ");
        System.out.println();
    }

    public static boolean isSorted(Comparable[] a){
        for(int i = 1;i < a.length;i ++)
            if(less(a[i],a[i-1])) return false;
        return true;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Random random = new Random();
        Integer[] a = new Integer[10000];
        for(int i = 0;i < 10000; i ++){
            a[i] = random.nextInt(100000);
        }
        System.out.println(time("merge",a));
//        System.out.println(time("insert1",a.clone()));
//        System.out.println(time("insert2",a));
        show(a);
    }
}
